package dp;

import java.util.Arrays;

public class LCSubseeuence {
    //最长公共子序列
    public static void main(String[] args) {

        System.out.println(longestCommonSubsequence("abcxyz", "abcxy"));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        int max=0;
        for (int i = 1; i <text1.length()+1; i++) {
            for (int j = 1; j <text2.length()+1; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max=Integer.max(max,dp[i][j]);
                } else {
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];

    }

    private static void print(int[][] dp) {
        System.out.println("=====");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("=====");
    }
}
